#include <iostream>
#include <algorithm>

void gnomeSort(int *a, const int N) {
    int curr_pos = 0;
    while (true) {
        if (curr_pos >= N)
            break;
        if (curr_pos == 0 || a[curr_pos] >= a[curr_pos - 1])
            curr_pos++;
        else {
            std::swap(a[curr_pos - 1], a[curr_pos]);
            curr_pos--;
        }
   }
}

void print(int *a, const int N) {
    for (int i = 0; i < N; i++)
        std::cout << a[i] << " ";
    std::cout << std::endl;
}

int main() {
    const int N = 6;
    int *a = new int[N] {1, 10, 8, 17, 4, 3};

    print(a, N);
    gnomeSort(a, N);
    print(a, N);

    delete[] a;

    return 0;
}